# LeetCode 144、二叉树的前序遍历
# 一、题目描述
给你二叉树的根节点 root ，返回它节点值的 前序、中序、后序 遍历。
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的前序遍历（ LeetCode 144） : https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
// 设置一个数组用来保存二叉树前序遍历的结果
List<Integer> preorderReslut = new ArrayList<>();
// 设置一个数组用来保存二叉树中序遍历的结果
List<Integer> inorderResult = new ArrayList<>();
// 设置一个数组用来保存二叉树后序遍历的结果
List<Integer> postorderResult = new ArrayList<>();
// 设置一个栈，用来保存路径
Stack<TreeNode> stack = new Stack<>();
// 设置一个节点，一开始指向根节点
TreeNode node = root;
// 设置三种状态，方便表示当前遍历当前节点的时候进行到哪一步了
// 每个节点都有 左、右、上 这三种状态
// 按照 左 --> 右 --> 上 的顺序观察每个节点
// 左代表该节点的左右孩子节点都没有遍历
int nodeLeft = 100;
// 右代表该节点的左孩子节点已经遍历，右孩子节点还没有遍历
int nodeRight = 200;
// 上代表左右孩子节点都已经遍历，需要返回到它的父节点
int nodeUp = 300;
// 每个节点的初始化状态都是从 左 开始
int nodeState = nodeLeft;
// 对二叉树进行遍历
while(node != null){
// 位置 ①
// 如果当前节点的状态是【左】，说明该节点的左右孩子节点都没有遍历
if(nodeState == nodeLeft){
// 把当前节点加入到二叉树前序遍历的结果数组中
preorderReslut.add(node.val);
// 如果当前节点有左子树
if(node.left != null){
// 先把当前节点加入到栈中，用来记录节点移动的路径
stack.push(node);
// 开始观察当前节点的左孩子节点，代码来到了位置 ①
node = node.left;
}else{
// 如果当前节点没有左子树，切换当前节点的状态为【右】
// 代码来到了位置 ①
nodeState = nodeRight;
}
}else if(nodeState == nodeRight){ // 如果当前节点的状态是【右】，说明该节点的左孩子节点已经遍历，右孩子节点还没有遍历
// 把当前节点加入到二叉树中序遍历的结果数组中
// inorderResult.add(node.val);
// 如果当前节点有右子树
if(node.right != null){
// 先把当前节点加入到栈中，用来记录节点移动的路径
stack.push(node);
// 开始观察当前节点的右孩子节点
node = node.right;
// 每个节点开始的状态都是【左】开始，所以需要重新设置一下节点的状态
nodeState = nodeLeft;
// 执行完上面三行代码，代码来到了位置 ①
}else{
// 如果当前节点没有右子树，切换当前节点的状态为【上】
// 代码来到了位置 ①
nodeState = nodeUp;
}
}else if(nodeState == nodeUp){ // 如果当前节点的状态是【上】，说明左右孩子节点都已经遍历，需要返回到它的父节点
// 把当前节点加入到二叉树后序遍历的结果数组中
//postorderResult.add(node.val);
// 需要返回到当前节点的父节点位置，通过栈顶元素来获取当前节点的父节点
// 首先构建一个空的节点
TreeNode parent = null;
// 如果栈中有元素
if(!stack.isEmpty()){
// 那么，栈顶元素就是当前节点的父节点
parent = stack.pop();
// 判断一下父节点的左节点是否为当前节点
// 比如这颗二叉树
// 1
// / \
// 2 3
// / \ \
// 4 5 6
// 如果当前节点是 4 ，那么 4 的父节点是 2，2 的左孩子节点是 4，此时需要切换状态为【右】
// 如果当前节点是 5 ，那么 5 的父节点是 2，2 的左孩子节点是 4，此时不需要切换状态
// 如果父节点的左节点为当前节点
if(parent.left == node){
// 切换当前节点的状态为【右】
nodeState = nodeRight;
}
}
// 开始观察当前节点的父节点
// 如果上述代码中栈中有元素，那么 parent 有值，代码来到了位置 ①
// 如果上述代码中栈中没有元素，那么 parent 没有值，会跳出循环
node = parent;
}
}
// 根据题目要求，返回二叉树前序、中序、后序遍历的结果
return preorderReslut;
}
}
# 2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的前序遍历（ LeetCode 144） : https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
// 设置一个数组用来保存二叉树前序遍历的结果
vector<int> preorderReslut;
// 设置一个数组用来保存二叉树中序遍历的结果
vector<int> inorderResult;
// 设置一个数组用来保存二叉树后序遍历的结果
vector<int> postorderResult;
// 设置一个栈，用来保存路径
stack<TreeNode*> st;
// 设置一个节点，一开始指向根节点
TreeNode* node = root;
// 设置三种状态，方便表示当前遍历当前节点的时候进行到哪一步了
// 每个节点都有 左、右、上 这三种状态
// 按照 左 --> 右 --> 上 的顺序观察每个节点
// 左代表该节点的左右孩子节点都没有遍历
int nodeLeft = 100;
// 右代表该节点的左孩子节点已经遍历，右孩子节点还没有遍历
int nodeRight = 200;
// 上代表左右孩子节点都已经遍历，需要返回到它的父节点
int nodeUp = 300;
// 每个节点的初始化状态都是从 左 开始
int nodeState = nodeLeft;
// 对二叉树进行遍历
while(node != NULL){
// 位置 ①
// 如果当前节点的状态是【左】，说明该节点的左右孩子节点都没有遍历
if(nodeState == nodeLeft){
// 把当前节点加入到二叉树前序遍历的结果数组中
preorderReslut.push_back(node->val);
// 如果当前节点有左子树
if(node->left != NULL){
// 先把当前节点加入到栈中，用来记录节点移动的路径
st.push(node);
// 开始观察当前节点的左孩子节点，代码来到了位置 ①
node = node->left;
}else{
// 如果当前节点没有左子树，切换当前节点的状态为【右】
// 代码来到了位置 ①
nodeState = nodeRight;
}
}else if(nodeState == nodeRight){ // 如果当前节点的状态是【右】，说明该节点的左孩子节点已经遍历，右孩子节点还没有遍历
// 把当前节点加入到二叉树中序遍历的结果数组中
// inorderResult.push_back(node->val);
// 如果当前节点有右子树
if(node->right != NULL){
// 先把当前节点加入到栈中，用来记录节点移动的路径
st.push(node);
// 开始观察当前节点的右孩子节点
node = node->right;
// 每个节点开始的状态都是【左】开始，所以需要重新设置一下节点的状态
nodeState = nodeLeft;
// 执行完上面三行代码，代码来到了位置 ①
}else{
// 如果当前节点没有右子树，切换当前节点的状态为【上】
// 代码来到了位置 ①
nodeState = nodeUp;
}
}else if(nodeState == nodeUp){ // 如果当前节点的状态是【上】，说明左右孩子节点都已经遍历，需要返回到它的父节点
// 把当前节点加入到二叉树后序遍历的结果数组中
//postorderResult.add(node.val);
// 需要返回到当前节点的父节点位置，通过栈顶元素来获取当前节点的父节点
// 首先构建一个空的节点
TreeNode* parent = NULL;
// 如果栈中有元素
if(!st.empty()){
// 那么，栈顶元素就是当前节点的父节点
parent = st.top();
st.pop();
// 判断一下父节点的左节点是否为当前节点
// 比如这颗二叉树
// 1
// / \
// 2 3
// / \ \
// 4 5 6
// 如果当前节点是 4 ，那么 4 的父节点是 2，2 的左孩子节点是 4，此时需要切换状态为【右】
// 如果当前节点是 5 ，那么 5 的父节点是 2，2 的左孩子节点是 4，此时不需要切换状态
// 如果父节点的左节点为当前节点
if(parent->left == node){
// 切换当前节点的状态为【右】
nodeState = nodeRight;
}
}
// 开始观察当前节点的父节点
// 如果上述代码中栈中有元素，那么 parent 有值，代码来到了位置 ①
// 如果上述代码中栈中没有元素，那么 parent 没有值，会跳出循环
node = parent;
}
}
// 根据题目要求，返回二叉树前序、中序、后序遍历的结果
return preorderReslut;
}
};
# 3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 二叉树的前序遍历（ LeetCode 144） : https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
# 设置一个数组用来保存二叉树前序遍历的结果
preorderReslut = []
# 设置一个数组用来保存二叉树中序遍历的结果
inorderResult = []
# 设置一个数组用来保存二叉树后序遍历的结果
postorderResult = []
# 设置一个栈，用来保存路径
stack = list()
# 设置一个节点，一开始指向根节点
node = root
# 设置三种状态，方便表示当前遍历当前节点的时候进行到哪一步了
# 每个节点都有 左、右、上 这三种状态
# 按照 左 --> 右 --> 上 的顺序观察每个节点
# 左代表该节点的左右孩子节点都没有遍历
nodeLeft = 100
# 右代表该节点的左孩子节点已经遍历，右孩子节点还没有遍历
nodeRight = 200
# 上代表左右孩子节点都已经遍历，需要返回到它的父节点
nodeUp = 300
# 每个节点的初始化状态都是从 左 开始
nodeState = nodeLeft
# 对二叉树进行遍历
while node :
# 位置 ①
# 如果当前节点的状态是【左】，说明该节点的左右孩子节点都没有遍历
if nodeState == nodeLeft :
# 把当前节点加入到二叉树前序遍历的结果数组中
preorderReslut.append(node.val)
# 如果当前节点有左子树
if node.left :
# 先把当前节点加入到栈中，用来记录节点移动的路径
stack.append(node)
# 开始观察当前节点的左孩子节点，代码来到了位置 ①
node = node.left
else:
# 如果当前节点没有左子树，切换当前节点的状态为【右】
# 代码来到了位置 ①
nodeState = nodeRight
elif nodeState == nodeRight:
# 如果当前节点的状态是【右】，说明该节点的左孩子节点已经遍历，右孩子节点还没有遍历
# 把当前节点加入到二叉树中序遍历的结果数组中
# inorderResult.add(node.val)
# 如果当前节点有右子树
if node.right :
# 先把当前节点加入到栈中，用来记录节点移动的路径
stack.append(node)
# 开始观察当前节点的右孩子节点
node = node.right
# 每个节点开始的状态都是【左】开始，所以需要重新设置一下节点的状态
nodeState = nodeLeft
# 执行完上面三行代码，代码来到了位置 ①
else:
# 如果当前节点没有右子树，切换当前节点的状态为【上】
# 代码来到了位置 ①
nodeState = nodeUp
elif nodeState == nodeUp :
# 如果当前节点的状态是【上】，说明左右孩子节点都已经遍历，需要返回到它的父节点
# 把当前节点加入到二叉树后序遍历的结果数组中
# postorderResult.add(node.val)
# 需要返回到当前节点的父节点位置，通过栈顶元素来获取当前节点的父节点
# 首先构建一个空的节点
parent = None
# 如果栈中有元素
if stack :
# 那么，栈顶元素就是当前节点的父节点
parent = stack.pop()
# 判断一下父节点的左节点是否为当前节点
# 比如这颗二叉树
# 1
# / \
# 2 3
# / \ \
# 4 5 6
# 如果当前节点是 4 ，那么 4 的父节点是 2，2 的左孩子节点是 4，此时需要切换状态为【右】
# 如果当前节点是 5 ，那么 5 的父节点是 2，2 的左孩子节点是 4，此时不需要切换状态
# 如果父节点的左节点为当前节点
if parent.left == node :
# 切换当前节点的状态为【右】
nodeState = nodeRight
# 开始观察当前节点的父节点
# 如果上述代码中栈中有元素，那么 parent 有值，代码来到了位置 ①
# 如果上述代码中栈中没有元素，那么 parent 没有值，会跳出循环
node = parent
# 根据题目要求，返回二叉树前序、中序、后序遍历的结果
return preorderReslut